PC Media 7/PC MEDIA CD07.iso/share/prog/cm/cmbtree.cpp

C/C++ Source or Header | 1994-09-06 | 19.6 KB | 669 lines

// CmBTree.cpp
// -----------------------------------------------------------------
// Compendium - C++ Container Class Library
// Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
// -----------------------------------------------------------------
// Balanced tree implementation.
// -----------------------------------------------------------------

#include <cm/include/cmbtree.h>


// "CmBTree" is the default tree constructor.
// (BTree order can not be less than 3).
//
CmBTree::CmBTree(unsigned ordr)
{
  _order = (ordr >= 3) ? ordr : 3;
  _root  = NULL;
}


// "CmBTree" is the tree copy constructor.
//
CmBTree::CmBTree(const CmBTree& T)
{
  _order = T._order;
  _root  = NULL;
  copy(T);
}


// "~CmBTree" is the tree destructor.
//
CmBTree::~CmBTree()
{
  removeAll();
}


// "=" assignment operator copies the specified tree into this tree.
//
CmBTree& CmBTree::operator=(const CmBTree& T)
{
  if (&T != this)
  {
    removeAll();
    _order = T._order;
    copy(T);
  }
  return *this;
}


// "height" returns the current tree height.
//
unsigned CmBTree::height() const
{
  CmBTreeNode *rover = _root;
  unsigned     ht    = 0;
  while (rover)
  {
    ht++;
    rover = rover->_children[0];
  }
  return ht;
}


// "add" adds a new object to the tree.
//
Bool CmBTree::add(CmObject* pObj)
{
  CmObject    *data  = pObj;                // Initialize data object.
  CmBTreeNode *child = NULL;                // Initialize child.
  CmBTreeNode *rover = nodeSearch(pObj);    // Find node to insert into.
  Bool         done  = FALSE;               // Loop flag.

  while (rover && !done)                    // Loop.
  {
    int idx = rover->shouldGo(data);        // Get position for new object.
    rover->addAt(idx, data, child, 1);      // Add new data and child to node.
    if (rover->_total <= _order-1)          // Data fits so exit.
      done = TRUE;
    else
    {
      data = rover->_data[(rover->_total) / 2];     // Data doesn't fit.
      CmBTreeNode *newRight = rover->split(_order); // Split the node.
      if (!newRight) return FALSE;                  // Split unsuccessful.
      child = newRight;                             // Set new child to right.
      rover = rover->_parent;                       // Move to parent.
    }
  }

  if (!done)                                    // Not done, create a
  {                                             // new root.
    CmBTreeNode *newRoot  = new CmBTreeNode(NULL, _order);
    newRoot->_children[0] = _root;              // Old root is child of new.
    newRoot->_children[1] = child;              // Stray child is also child.
    newRoot->_data    [0] = data;               // Data is lone root object.
    newRoot->_total       = 1;                  // New root contains 1.

    if (_root)                                  // Set parentage of children
    {                                           // if not first time in.
      child->_parent = newRoot;
     _root->_parent  = newRoot;
    }
    _root = newRoot;                            // New root is now root.
  }
  _size++;                                      // Bump size and split.
  return TRUE;
}


// "remove" removes the first occurrence of an object that isEqual
// to the specified object from the tree.
//
Bool CmBTree::remove(CmObject* pObj)
{
  CmBTreeNode *node = lookupNode(pObj);         // Find node where object is.
  if (!node) return FALSE;                      // No object, exit.

  int idx = node->index(pObj);                  // Get index of object in node.
  if (idx == -1) return FALSE;                  // No object, exit.
  if (ownsObjects()) delete node->_data[idx];   // Delete object if owned.
  _size--;                                      // Decrement size.

  if (node->_children[0])                       // If node is not leaf, swap
  {                                             // object with object at left
    CmBTreeNode *rover = node->_children[idx+1];  // most side of right branch.
    while (rover->_children[0]) rover = rover->_children[0];
    node->_data[idx] = rover->_data[0];
    node = rover;
    idx  = 0;
  }

  node->removeAt(idx);                         // Remove object from node.
  unsigned minkeys = minKeys(_order);          // Save min allowable keys.

  while (node != _root && node->_total < minkeys)  // Start looping if number
  {                                                // of keys fell below min.
    int nodeIdx = node->_parent->index(node);  // Save index of node in parent.
    if (nodeIdx == -1) return FALSE;

    if (node->_parent->_children[nodeIdx+1])   // If node has a right sibling,
    {
      CmBTreeNode *sib = node->_parent->_children[nodeIdx+1];
      CmBTreeNode *par = node->_parent;

      // If the right sibling has keys to spare, move the left most key in
      // the right sibling up to the parent.  Take the parent key parenting
      // this node and move that key into this node.  Exit.
      if (sib->_total > minkeys)
      {
        node->addAt(node->_total, par->_data[nodeIdx], sib->_children[0], 1);
        if (sib->_children[0]) sib->_children[0]->_parent = node;
        par->_data[nodeIdx] = sib->_data[0];
        sib->removeAt(0);
        return TRUE;
      }

      // The right sibling has no keys to spare, so we need to combine the
      // remaining keys in this node with the parent key parenting this node
      // and the keys of the right sibling to form one node.
      node->addAt(node->_total, par->_data[nodeIdx], sib->_children[0], 1);
      for (int ii = 0; ii < sib->_total; ii++)
      {
        node->addAt(node->_total, sib->_data[ii], sib->_children[ii+1], 1);
        if (sib->_children[ii+1]) sib->_children[ii+1]->_parent = node;
      }
      delete sib;
      par->removeAt(nodeIdx);
      node = par;
    }

    else if (node->_parent->_children[nodeIdx-1]) // If node has left sibling,
    {
      CmBTreeNode *sib = node->_parent->_children[nodeIdx-1];
      CmBTreeNode *par = node->_parent;

      // If the left sibling has keys to spare, move the right most key in
      // the left sibling up to the parent.  Take the parent key parenting
      // the left sibling and move that key into this node.  Exit.
      if (sib->_total > minkeys)
      {
        node->addAt(0, par->_data[nodeIdx-1], sib->_children[sib->_total], 0);
        if (sib->_children[sib->_total])
          sib->_children[sib->_total]->_parent = node;
        par->_data[nodeIdx-1] = sib->_data[sib->_total-1];
        sib->removeAt(sib->_total-1);
        return TRUE;
      }

      // The left sibling has no keys to spare, so we need to combine the
      // keys in the left sibling with the parent key parenting the left
      // sibling and the keys of this node to form one node.
      sib->addAt(sib->_total, par->_data[nodeIdx-1], node->_children[0], 1);
      for (int ii = 0; ii < node->_total; ii++)
      {
        sib->addAt(sib->_total, node->_data[ii], node->_children[ii+1], 1);
        if (node->_children[ii+1]) node->_children[ii+1]->_parent = sib;
      }
      delete node;
      par->removeAt(nodeIdx-1);
      node = par;
    }
  }

  if (node->_total == 0)                // If only the root node is left,
  {                                     // and it has no keys, then delete
    CmBTreeNode *temp = _root;          // delete the root node and make
    _root = _root->_children[0];        // it's left most child the new
    delete temp;                        // root node.
  }
  if (_root && _root->_parent) _root->_parent = NULL;
  return TRUE;
}


// "lookup" returns the first occurrence of an object which isEqual
// to the specified object.
//
CmObject* CmBTree::lookup(CmObject* pObj) const
{
  if (!pObj || !_root) return NULL;

  CmBTreeNode *node = lookupNode(pObj);    // Find node where object is.
  if (!node) return NULL;

  int idx = node->index(pObj);
  return (idx == -1) ? NULL : node->_data[idx];
}


// "contains" checks to see if an object that isEqual to the specified
// object exists in the tree.
//
Bool CmBTree::contains(CmObject* pObj) const
{
  if (!pObj || !_root) return NULL;

  CmBTreeNode *node = lookupNode(pObj);    // Find node where object is.
  if (!node) return FALSE;

  int idx = node->index(pObj);
  return (idx != -1) ? TRUE : FALSE;
}


// "occurrences" returns the number of objects in the tree
// isEqual to the specified object.
//
unsigned CmBTree::occurrences(CmObject* pObj) const
{
  unsigned        occur    = 0;
  CmBTreeIterator iterator(*this);
  while (!iterator.done())
  {
    CmObject *temp = iterator.next();
    if (pObj->compare(temp) == 0) occur++;
  }
  return occur;
}


// "removeAll" removes all objects from the tree.
//
void CmBTree::removeAll()
{
  removeNodes(_root, ownsObjects());
  _root = NULL;
  _size = 0;
}


// "newIterator" creates and returns a new tree iterator.
//
CmIterator* CmBTree::newIterator() const
{
  return new CmBTreeIterator(*this);
}


// "nodeSearch" searches for and returns a pointer to the node
// where the specified object is to be inserted.
//
CmBTreeNode* CmBTree::nodeSearch(CmObject* pObj) const
{
  CmBTreeNode *rover = _root;
  CmBTreeNode *found = NULL;

  while (rover && !found)
  {
    int idx = rover->shouldGo(pObj);
    if (rover->_children[idx]) rover = rover->_children[idx];
    else                       found = rover;
  }
  return found;
}


// "lookupNode" returns a pointer to the node where the first occurrence
// of an object isEqual to the specified object was found.
//
CmBTreeNode* CmBTree::lookupNode(CmObject* pObj) const
{
  if (!pObj || !_root) return NULL;

  CmBTreeNode *rover = _root;             // Start at root node.
  CmBTreeNode *ret   = NULL;
  while (rover && !ret)
  {
    int idx = rover->index(pObj);         // Is object in node?
    if (idx != -1)
      ret = rover;                        // Yes.
    else
    {
      idx   = rover->shouldGo(pObj);      // No.  Set node to point to
      rover = rover->_children[idx];      // child where object would be.
    }
  }
  return ret;
}


// "lookupAbs" returns a pointer to the node where the exact object
// specified was found (addresses are compared always).
//
CmBTreeNode* CmBTree::lookupAbs(CmObject* pObj) const
{
  if (!pObj || !_root) return NULL;

  CmBTreeNode *rover = _root;             // Start at root node.
  CmBTreeNode *ret   = NULL;
  while (rover && !ret)
  {
    int idx = rover->indexAbs(pObj);      // Is object in node?
    if (idx != -1)
      ret = rover;                        // Yes.
    else
    {
      idx   = rover->shouldGo(pObj);      // No.  Set node to point to
      rover = rover->_children[idx];      // child where object would be.
    }
  }
  return ret;
}


// "removeNodes" recursively calls itself to remove the nodes below
// the specified node and also deletes the specified node.
//
void CmBTree::removeNodes(CmBTreeNode* pNode, Bool owns)
{
  if (pNode)
  {
    for (int ii = 0; ii < pNode->_total; ii++)
    {
      if (owns) delete pNode->_data[ii];
      removeNodes(pNode->_children[ii], owns);
    }
    removeNodes(pNode->_children[pNode->_total], owns);
    delete pNode;
  }
}


// "CmBTreeNode" is the constructor for the node class.
//
CmBTreeNode::CmBTreeNode(CmBTreeNode* parent, unsigned order)
{
  _total    = 0;
  _parent   = parent;
  _data     = new CmObject*   [order];
  _children = new CmBTreeNode*[order+1];
  if (_data && _children) clear(order);
}


// "~CmBTreeNode" is the destructor for the node class.
//
CmBTreeNode::~CmBTreeNode()
{
  delete[] _data;
  delete[] _children;
}


// "shouldGo" returns the index of where the specified object would
// be inserted into the data list if add were called.
//
int CmBTreeNode::shouldGo(CmObject* pObj) const
{
  if (!pObj)       return -1;
  if (_total == 0) return 0;

  if (pObj->compare(_data[0])        <  0) return 0;
  if (pObj->compare(_data[_total-1]) >= 0) return _total;

  int idx = -1;
  int ii  = _total-1;
  while (ii >= 0 && idx == -1)
    if (pObj->compare(_data[ii--]) >= 0) idx = ii+2;
  return idx;
}


// "index" returns the index in the data list of the first occurrence
// of an object isEqual to the specified object.
//
int CmBTreeNode::index(CmObject* pObj) const
{
  if (_total == 0 || !pObj) return -1;
  int idx = -1;
  int ii  = 0;
  while (ii < _total && idx == -1)
    if (pObj->compare(_data[ii++]) == 0) idx = ii-1;
  return idx;
}


// "indexAbs" returns the index in the data list of the exact object
// specified (addresses are compared always).
//
int CmBTreeNode::indexAbs(CmObject* pObj) const
{
  if (_total == 0 || !pObj) return -1;
  int idx = -1;
  int ii  = 0;
  while (ii < _total && idx == -1)
    if (pObj == _data[ii++]) idx = ii-1;
  return idx;
}


// "index" returns the index in the child list of the specified node.
//
int CmBTreeNode::index(CmBTreeNode* pNode) const
{
  if (_total == 0 || !pNode) return -1;
  int idx = -1;
  int ii  = 0;
  while (ii <= _total && idx == -1)
    if (pNode == _children[ii++]) idx = ii-1;
  return idx;
}


// "addAt" adds the specified object/child to this node's lists at the
// specified index.
//
Bool CmBTreeNode::addAt(int idx, CmObject* pObj, CmBTreeNode* pNode, int offset)
{
  if (offset == 0) _children[_total+1] = _children[_total];
  for (int ii = _total; ii > idx; ii--)     // Slide other stuff to make
  {                                         // room.
    _data    [ii       ] = _data    [ii-1];
    _children[ii+offset] = _children[ii+offset-1];
  }

  _data    [idx       ] = pObj;             // Insert object and child.
  _children[idx+offset] = pNode;
  _total++;
  return TRUE;
}


// "removeAt" removes the object at the specified index in the node's
// data list and removes the right child of that object.
//
Bool CmBTreeNode::removeAt(int idx)
{
  if (idx < 0 || idx >= _total) return FALSE;

  for (int ii = idx; ii < _total-1; ii++)
  {
    _data    [ii  ] = _data    [ii+1];
    _children[ii+1] = _children[ii+2];
  }
  _data    [_total-1] = NULL;
  _children[_total  ] = NULL;
  _total--;
  return TRUE;
}


// "clear" nulls out the data and child arrays in this node.
//
void CmBTreeNode::clear(int order)
{
  for (int ii = 0; ii <= order; ii++)
  {
    if (ii < order) _data[ii] = NULL;
    _children[ii] = NULL;
  }
}


// "split" is called to split this tree node.
//
CmBTreeNode* CmBTreeNode::split(unsigned ordr)
{
  CmBTreeNode *newRight = new CmBTreeNode(_parent, ordr);
  if (!newRight) return NULL;

  int ix = 0, midIdx = _total / 2;
  for (int ii = midIdx+1; ii <= _total; ii++, ix++)
  {
    if (ii != _total)
    {
      newRight->_data[ix] = _data[ii];
      newRight->_total++;
      _data[ii] = NULL;
    }
    newRight->_children[ix] = _children[ii];
    _children[ii] = NULL;
    if (newRight->_children[ix]) newRight->_children[ix]->_parent = newRight;
  }
  _total = midIdx;
  return newRight;
}


// "CmBTreeIterator" is the constructor for the iterator class.
//
CmBTreeIterator::CmBTreeIterator(const CmBTree &Tr) : _tree(Tr)
{
  _node  = _tree._root;
  _index = 0;
  if (_node)                                 // Descend all the way down left.
    while (_node->_children[0])
      _node = _node->_children[0];
}


// "next" returns the current object and advances the iterator to the
// next object.
//
CmObject* CmBTreeIterator::next()
{
  CmObject* retValue = current();             // Save current object.
  if (!retValue) return NULL;

  if (_node->_children[_index+1])             // Traverse all the way down
  {                                           // the left part of the next
    _node = _node->_children[_index+1];       // child branch.
    while (_node->_children[0])
      _node = _node->_children[0];
    _index = 0;
    return retValue;
  }

  if (_index < _node->_total-1)               // No child branches, but there
  {                                           // are still objects in this
    _index++;                                 // node so bump the index and
    return retValue;                          // exit.
  }

  Bool done = FALSE;                          // Need to back up the tree.
  while (!done)
  {
    if (!_node->_parent)                      // If node has no parent, we
    {                                         // are done iterating.
      _node = NULL;
      done  = TRUE;
    }

    else                                      // Node has parent.
    {
      int idx = _node->_parent->index(_node); // What branch were we just in?
      if (idx == -1)                          // Error! - shouldn't happen.
      {
        _node = NULL;
        done  = TRUE;
      }
      else                                    // Got the branch.
      {
        _node = _node->_parent;               // Move up to parent.
        if (idx < _node->_total)              // If not end of data list,
        {                                     // bump index and exit.
          _index = idx;
          done = TRUE;
        }
      }
    }
  }
  return retValue;                            // Return the object.
}


// "previous" backs the iterator up one object and returns that object.
//
CmObject* CmBTreeIterator::previous()
{
  CmObject* retValue = current();             // Save current object.
  if (!retValue) return NULL;

  if (_node->_children[_index])               // Traverse all the way down
  {                                           // the right part of the
    _node = _node->_children[_index];         // previous child branch.
    while (_node->_total && _node->_children[_node->_total-1])
      _node = _node->_children[_node->_total];
    _index = _node->_total-1;
    return retValue;
  }

  if (_index > 0)                             // No child branches, but there
  {                                           // are still objects in this
    _index--;                                 // node so decrement the index
    return retValue;                          // and exit.
  }

  Bool done = FALSE;                          // Need to back up the tree.
  while (!done)
  {
    if (!_node->_parent)                      // If node has no parent, we
    {                                         // are done iterating.
      _node = NULL;
      done  = TRUE;
    }

    else                                      // Node has parent.
    {
      int idx = _node->_parent->index(_node); // What brach were we just in?
      if (idx == -1)                          // Error! - shouldn't happen.
      {
        _node = NULL;
        done  = TRUE;
      }
      else                                    // Got the branch.
      {
        _node = _node->_parent;               // Move up to parent.
        if (idx > 0)                          // If not at beginning,
        {                                     // decrement index and exit.
          _index = idx - 1;
          done   = TRUE;
        }
      }
    }
  }
  return retValue;                            // Return the object.
}


// "first" moves the iterator to the first object in the tree.
//
void CmBTreeIterator::first()
{
  _node  = _tree._root;
  _index = 0;

  if (_node)
    while (_node->_children[0])
      _node = _node->_children[0];
}


// "last" moves the iterator to the last object in the tree.
//
void CmBTreeIterator::last()
{
  _node = _tree._root;
  if (_node)
  {
    while (_node->_children[_node->_total])
      _node = _node->_children[_node->_total];
    _index = _node->_total - 1;
  }
}